


import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;



public class NaiveSolutionFinder implements SolutionFinder 
{
	
//	private class MovePushCord
//	{
//		Cord lastPushCord;
//		Move move;
//		
//		private MovePushCord( Cord lastPusCord, Move move )
//		{
//			this.lastPushCord = lastPusCord;
//			this.move = move;
//		}
//	}
	
//	private class BoardWithPath
//	{
//		Board board;
//		String path;
//	}
	
	
	
//	private long hash( Board board )
//	{
//		
//		BoardImplFast fastBoard = (BoardImplFast) board;
//		
//		byte[] hashArray = new byte[2+(fastBoard.getBoxesCoords().length*2)];
//		
//		hashArray[0] = (byte) board.getPlayer().getX();
//		hashArray[1] = (byte) board.getPlayer().getY();
//		
//		
//		int counter = 0;
//		for ( short box : fastBoard.getBoxesCoords() )
//		{
//			counter += 2;
//			
//			hashArray[ counter ] = (byte) CordImpl.getXFromCords(box);
//			hashArray[ counter+1 ] = (byte) CordImpl.getYFromCords(box);
//			
//		}
//		
////		short[] hashArray = new short[1+fastBoard.getBoxesCoords().length];
////		
////		hashArray[0] = CordImpl.getCoordsFromXY( fastBoard.getPlayer().getX() , fastBoard.getPlayer().getY());
////		
////		int counter = 0;
////		for ( short box : fastBoard.getBoxesCoords() )
////		{
////			counter++;
////			hashArray[counter] = box;
////			
////		}
////		
//		return Arrays.hashCode(hashArray);
//		
////		int x = fastBoard.getPlayer().getX();
////		int y = fastBoard.getPlayer().getY();
////		
////		int playerCoords = CordImpl.getCoordsFromXY( fastBoard.getPlayer().getX() , fastBoard.getPlayer().getY());
////		int boxCoords = fastBoard.getBoxesCoords()[0];
////		
////		int hash = ( playerCoords | ( boxCoords << 8 ) );
////		
////		return hash;
//
//	}
	
	private boolean finished = false;
	private String solution = "";
//	VisitedCellHelper visited;
	NaiveMove naiveMoveRule = new NaiveMove();
	
//	HashSet<Integer> visitedSet = new HashSet<Integer>();
	HashSet<Integer> visitedSet = new HashSet<Integer>();
	
//	private boolean finished( Cord[] boxes, Cord[] goals )
//	{
//		
//		for ( Cord box : boxes )
//		{
//			
//			boolean contains = false;
//			for ( Cord goal : goals )
//			{
//				if ( box.equalsCord(goal))
//				{
//					contains = true;
//				}
//			}
//			
//			if ( !contains )
//			{
//				return false;
//			}
//			
//		}
//		
//		return true;
//	}
		
	public void DFS( Board board, String path )
	{
		
		if ( finished )
		{
			return;
		}
		
//		if ( visitedSet.contains( hash(board) ) )
		if ( visitedSet.contains( board.hashCode() ) )
		{
			return;
		}
		else
		{
//			visitedSet.add( hash(board) );
			visitedSet.add( board.hashCode() );
		}
		
//		board.printBoard();
//		System.out.println("player: "+board.getPlayer());
		
//		if ( board.getBoxes().containsAll( board.getGoals() ) )
//		if ( Arrays.equals( ) )
//		if ( finished( board.getBoxes() , board.getGoals() ) )
		if ( board.isFinished() )
		{
			System.out.println("alla boxar paa alla goals");
			finished = true;
			solution = path;
			return;
		}
		
		List<Move> moves = board.getLegalMoves( board.getPlayer() , naiveMoveRule);
//		for ( Move move : board.getLegalMoves( board.getPlayer() , naiveMoveRule) )
		for ( Move move : moves )
		{
//			System.out.println("Move: "+ move.toString() );
			
//			if ( board.getCellType(move).isBox())
//			{
//				board.printBoard();
//			}
			if ( moves.size() == 1 )
			{
				board.doMovePlayer( move.getDirectionToThis() );
				
				DFS( board, path+move.getDirectionToThis().toString() );
			}
			else
			{
				Board newBoard = board.clone();
				
				newBoard.doMovePlayer( move.getDirectionToThis() );
				
				DFS( newBoard, path+move.getDirectionToThis().toString() );
			}

		}
		
	}
	
	private class BoardPath
	{
		Board board;
		String path;
		
		public BoardPath( Board board, String path )
		{
			this.board = board;
			this.path = path;
		}
	}
	
	public void BFS( Board board, String path, LinkedList<BoardPath> boxQueue, LinkedList<BoardPath> trololoQueue  )
	{
		
		if ( finished )
		{
			return;
		}
		
//		if ( visitedSet.contains( hash(board) ) )
		if ( visitedSet.contains( board.hashCode() ) )
		{
			return;
		}
		else
		{
//			visitedSet.add( hash(board) );
			visitedSet.add( board.hashCode() );
		}
		
//		if ( finished( board.getBoxes() , board.getGoals() ) )
		if ( board.isFinished() )
		{
			System.out.println("alla boxar paa alla goals");
			finished = true;
			solution = path;
			return;
		}
		
		for ( Move move : board.getLegalMoves( board.getPlayer() , naiveMoveRule) )
		{
//			System.out.println("Move: "+ move.toString() );
			
//			if ( board.getCellType(move).isBox())
//			{
//				board.printBoard();
//			}
			
			Board newBoard = board.clone();
			newBoard.doMovePlayer( move.getDirectionToThis() );
			
			boolean movesBox = false;
			
			if ( board.getCellType( move ).isBox() )
			{
				boxQueue.addLast( new BoardPath( newBoard, path+move.getDirectionToThis().toString() ) );
			}
			else
			{
//				System.out.println("omgZ");
				trololoQueue.addLast( new BoardPath( newBoard, path+move.getDirectionToThis().toString() ) );
			}

//			queue.addLast( new BoardPath( newBoard, path+move.getDirectionToThis().toString() ) );
//			DFS( newBoard, path+move.getDirectionToThis().toString() );
		}
	}
	
	public void BFS( Board oldBoard )
	{
		LinkedList<BoardPath> boxQueue = new LinkedList<BoardPath>();
		LinkedList<BoardPath> trololoQueue = new LinkedList<BoardPath>();
		
		boxQueue.addFirst( new BoardPath( oldBoard, "" ) );
		
		while ( ( !boxQueue.isEmpty() ) || ( !trololoQueue.isEmpty() ) )
		{

			BoardPath boardPath;
			if ( !boxQueue.isEmpty() )
			{
				boardPath = boxQueue.removeFirst();
			}
			else
			{
				boardPath = trololoQueue.removeFirst();
			}
			
			
			BFS( boardPath.board, boardPath.path, boxQueue, trololoQueue );
			
//			Board board = boardPath.board;
//			String path = boardPath.path;
//			
//			if ( finished )
//			{
//				return;
//			}
//			
//			if ( visitedSet.contains( hash(board) ) )
//			{
//				return;
//			}
//			else
//			{
//				visitedSet.add( hash(board) );
//			}
//			
//			if ( finished( board.getBoxes() , board.getGoals() ) )
//			{
//				System.out.println("alla boxar paa alla goals");
//				finished = true;
//				solution = path;
//				return;
//			}
//			
//			for ( Move move : board.getLegalMoves( board.getPlayer() , naiveMoveRule) )
//			{
////				System.out.println("Move: "+ move.toString() );
//				
////				if ( board.getCellType(move).isBox())
////				{
//					board.printBoard();
////				}
//				
//				Board newBoard = board.clone();
//				
//				newBoard.doMovePlayer( move.getDirectionToThis() );
//				
//				queue.addLast( new BoardPath( newBoard, path+move.getDirectionToThis().toString() ) );
////				DFS( newBoard, path+move.getDirectionToThis().toString() );
//			}
			
		}
		
	}
	
	/**
	 * Naive solution finder, expects a single goal and a single box.
	 */
	@Override
	public String FindSolution(Board board) 
	{

		board.printBoard();

		long before = System.currentTimeMillis();

//		System.out.println("boxes = "+board.getBoxes().length);
		
		DFS(board, "");
//		BFS(board);
		
//		for ( int i = 0; i < 1000; i++ )
//		{
//			Board newBoard = board.clone();
//		}
		
//		long time = System.nanoTime();
		
//		int n = 10000;
//		
//		for ( int i = 0; i < n; i++ )
//		{
//			Board newBoard = board.clone();
//		}
//		
//		System.out.println( "cloneTime = " + ((System.nanoTime()-time)/n) );
		
		
		System.out.println( "Time = " + (System.currentTimeMillis()-before) );
		
		
//		short[] array = new short []{1,2,3,5,6,7,8};
//		
//		System.out.println( "binsearch = "+Arrays.binarySearch(array, (short)4) );
//		
		
//		System.out.println(solution);
		
		return solution;
		
	}

}
